package sort;

import org.junit.Test;
import utils.CommonUtil;

public class LeetCode_LCR170 {
    private int count = 0;
    //归并排序思想，使用归并排序，记录逆序对对数即可
    public int reversePairs(int[] record) {
        if (record.length>1){
            mergeSort(record, 0, record.length-1);
        }
        return count;
    }

//    @Test
//    public void test() {
//        int[] arr = {9, 7, 5, 4, 6};
//        arr = mergeSort(arr, 0, arr.length-1);
//        System.out.println(count);
//        System.out.println(CommonUtil.printArray(arr));
//    }

    public int[] mergeSort(int[] arr, int left, int right) {
        if (left == right){
            return new int[]{arr[left]};
        }

        int mid = left + ((right - left)>>1);

        return merge(
                mergeSort(arr, left, mid),
                mergeSort(arr, mid+1, right)
        );
    }

    public int[] merge(int[] arr1, int[] arr2) {
        int i=0,j=0,k=0;
        int[] result = new int[arr1.length+arr2.length];
        while (i<arr1.length && j<arr2.length) {
            if (arr1[i] <= arr2[j]) {       //A<=B
                result[k++] = arr2[j++];
            }else {                         //A>B
                count += (arr2.length - j);  //记录逆序对对数
                result[k++] = arr1[i++];
            }
        }
        while (i<arr1.length) {
            result[k++] = arr1[i++];
        }
        while (j<arr2.length){
            result[k++] = arr2[j++];
        }
        return result;


    }


}
